#include <iostream>
#include <vector>
#include <stack>
#define NormalFind      0
#define PathCompress    1
#define StackCompress   2

#define FindType StackCompress

using namespace std;


class UnionFind
{
public:
    vector<int> parents;
    vector<int> size;
public:
    UnionFind(){}
    UnionFind(int n)
    {
        parents.resize(n);
        size.resize(n, 1);
        for(int i=0; i<n; i++)
        {
            parents[i] = i;
        }
    }
    ~UnionFind(){}

# if FindType == NormalFind
    int find(int x)
    {
        while(x!=parents[x])
        {
            x = parents[x];
        }
        return parents[x];
    }
#elif FindType == PathCompress
    int find(int x)
    {
        if(x!=parents[x])
        {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }
#else
    int find(int x)
    {
        stack<int> sta;
        while(x!=parents[x])
        {
            sta.push(x);
            x = parents[x];
        }   
        while(!sta.empty())
        {
            int tmp = sta.top();
            sta.pop();
            parents[tmp] = x;
        }
        return x;
    }
#endif 

    bool connect(int x, int y)
    {
        return find(x) == find(y);  // 判断是否在同一集合
    }

    void unite(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if(rootx == rooty) return ; // 已经在同一集合
        if(size[rootx] > size[rooty])
        {
            parents[rooty] = rootx;
            size[rootx]+=size[rooty];
        }
        else
        {
            parents[rootx] = rooty;
            size[rooty] +=size[rootx];
        }


    }


};

int main()
{

    UnionFind uf(10);
    uf.unite(1, 2);
    uf.unite(2, 3);
    uf.unite(3, 4);
    uf.unite(7, 9);
    uf.unite(4, 9);
    uf.unite(2, 6);
    cout << "connect ?"<< endl;
    cout << uf.connect(4, 6)  << endl;
    cout << uf.connect(1, 9)  << endl;
    cout << uf.connect(7, 3)  << endl;


    return 0;
}
